#include "dnsCache.h"
#include <stdexcept>

namespace dns
{

	const uint64_t DEFAULT_MAX_CACHE_SIZE = 5000000; //5MB
	const int DEFAULT_MAX_TTL = 604800; //1Week
	//const int DEFAULT_MIN_TTL = 15; //15sec

}

DNSCache::DNSCache(): size_( 0 ), maxSize_( dns::DEFAULT_MAX_CACHE_SIZE ),
	maxTTL_( dns::DEFAULT_MAX_CACHE_SIZE ), newestRecord_( NULL ), oldestRecord_( NULL )
{
	std::vector< CacheListNode* > sampleBucket; //for the sizeOfCalculation
	resizeSortedTTLList();
	//get the size of the empty data structures
	size_ += sizeof( answers_ );
	size_ += sizeof( authorities_ );
	size_ += sizeof( secondsPerBucket_ );
	size_ += sizeof( startTime_ );
	size_ += sizeof( newestRecord_ );
	size_ += sizeof( oldestRecord_ );
	size_ += sizeof( sampleBucket ) * ( maxTTL_/secondsPerBucket_ + 1 );
}

DNSCache::~DNSCache()
{
}

void DNSCache::setMaxSize( const uint64_t &size ) 
{
	maxSize_ = size;
	if( size > maxSize_ )
		cleanCache();
}

uint64_t DNSCache::maxSize() const 
{
	return maxSize_;
}

uint64_t DNSCache::size() const 
{
	return size_; 
}

void DNSCache::addAnswers( const std::string& question, std::vector< DNSRecord > rs )
{
	WriteLocker lock( recordLock_ );
	CacheListNode* node;
	if( answers_.find( question ) == answers_.end() )
	{
		//Doesn't already exist create entry.
		node = new CacheListNode();
	}
	else 
	{
		//udate entry
		node = answers_[ question ];
		//take out of list so that we can put it at the front
		node->previous()->setNext( node->next() );
		node->next()->setPrevious( node->previous() );
		size_ -= node->memorySize();
	}
	node->setRecords( rs );
	node->setPrevious( NULL );
	node->setNext( newestRecord_ );
	newestRecord_ = node; 
  if( oldestRecord_ == NULL ) 
	{
		oldestRecord_ = node; 
	}
	answers_[question] = node;
	addToTTLList( node );
	size_ += node->memorySize();
	if( size_ > maxSize_ )
		overSize();
}

void DNSCache::addAuthorities( const std::string& domain, std::vector< DNSRecord > auths )
{
	WriteLocker lock( recordLock_ );
	CacheListNode* node;
	if( authorities_.find( domain ) == authorities_.end() )
	{
		//Doesn't already exist create entry.
		node = new CacheListNode();
	}
	else 
	{
		//udate entry
		node = authorities_[ domain ];
		//take out of list
		node->previous()->setNext( node->next() );
		node->next()->setPrevious( node->previous() );
		size_ -= node->memorySize();
	}
	node->setQuery( domain );
	node->setRecords( auths );
	node->setPrevious( NULL );
	node->setNext( newestRecord_ );
	newestRecord_ = node; 
  if( oldestRecord_ == NULL ) 
	{
		oldestRecord_ = node; 
	}
	authorities_[domain] = node;
	addToTTLList( node );
	size_ += node->memorySize();
	if( size_ > maxSize_ )
		overSize();
}

void setCacheListNode( CacheListNode* node, const std::string &query, const
		std::vector< DNSRecord > &records )
{

}

std::vector< DNSRecord > DNSCache::answers( DNSQuestion q ) const
{
	std::vector< DNSRecord > records;
	ReadLocker lock( recordLock_ );
	if( answers_.find( q.queryName() ) == answers_.end() )
		return records;
	return answers_.at( q.queryName() )->records(); 
}

std::vector< std::string > DNSCache::split( const std::string &s, const char &delimiter ) const
{
	std::string workingString = s; 
	std::vector< std::string > list;
	//std::string::iterator itr;
	std::size_t pos;
	while( (pos = workingString.find( delimiter )) < workingString.size() )
	{
		std::string found = workingString.substr( workingString.size() - pos );
		workingString = workingString.substr( workingString.size() - pos, workingString.size() );
		list.push_back( found );
	}

	return list;
}

std::vector< DNSRecord > DNSCache::authorities( DNSQuestion q ) const
{
	std::vector< std::string > levels = split(q.queryName(), '.');
	ReadLocker lock( recordLock_ );

	for( uint32_t i = 0; i < levels.size(); ++i )
	{
		std::string domain;
		for( uint32_t k = i; k < levels.size(); ++k )
		{
			domain += levels[k] + ".";
		}
		domain = domain.substr( domain.size() - 1 ); //get rid of trailing .
		if( authorities_.find( domain ) != authorities_.end() )
		{
			const CacheListNode* node = authorities_.at( domain );
			return node->records();

			//return (authorities_[ domain ]->records());
		}
	}
	return std::vector< DNSRecord >();
}

void  DNSCache::cleanCache()
{
  //**MEANT TO ONLY BE RUN FROM A STAND ALONE THREAD FOR DOING CACHE MAINTANCE
	 
	/*************************************************************
	 * Sleep until oldestRecord_ expires.
	 * Wake and check the oldestRecord as it may have already been removed due to cache miss
	 * if it needs to be removed remove it and any other expired records
	 * Repeat
	 * ***********************************************************/

// Using a record of the query in the CacheListNode in order to keep from leaving dangling pointers 
// in answers_ and authorities_.

	//Treat sortedTTLs_ like a ring buffer where every element is a segment of time with index 0 starting at
	//startTime_ and going onward in secondsPerBucket_ amounts.
	while( true )
	{
		WriteLocker lock( recordLock_ );
		time_t now = time(NULL);
		int numberOfExpired =  ( now - startTime_ ) / secondsPerBucket_; 
		removeBuckets( numberOfExpired );
		startTime_ += numberOfExpired * secondsPerBucket_;
		int numberOfSecondsLeftToWait = startTime_+secondsPerBucket_ - now;
		lock.unlock();
		sleep( numberOfSecondsLeftToWait );
	}
}

void DNSCache::removeBuckets( const int &removeNum )
{
	std::vector< CacheListNode* > bucket;
	for( int i = 0; i < removeNum; ++i )
	{
		bucket = sortedTTLs_.front();
		for( uint32_t k = 0; k < bucket.size(); ++k )
		{
			bucket[k]->previous()->setNext( bucket[k]->next() );
			bucket[k]->next()->setPrevious( bucket[k]->previous() );
			answers_.erase( bucket[k]->query() );
			authorities_.erase( bucket[k]->query() );
			delete bucket[k];
		}
		sortedTTLs_.pop_front();
		sortedTTLs_.push_back( std::vector< CacheListNode* >() );
	}
}

void DNSCache::overSize()
{
	//Called from functions that already hold the lock. This function will
	//deadlock if requesting the lock
	
	if( size_ > maxSize_ )
	{ 
		uint64_t sizeOver = size_ - maxSize_;
		while( sizeOver > 0  && oldestRecord_ != NULL )
		{ //pop off the end
			if( oldestRecord_->previous() != NULL )
			{
				oldestRecord_ = oldestRecord_->previous();
				if( oldestRecord_->next()->memorySize() > sizeOver )
					sizeOver = 0;
				else
					sizeOver -= oldestRecord_->next()->memorySize();
			  removeNode( oldestRecord_->next() );
				oldestRecord_->setNext( NULL );
			}
			else
			{
				throw std::runtime_error( "Cache over size with one item in cache... GIVING UP" );
				return;
			}
		}
	}
}

void DNSCache::addToTTLList( CacheListNode* node )
{
	/****************************************************************
	 * Grab the expiration time.
	 * Determine the time since the start time of the sortedTTLs_
	 * find index by dividing by secondsPerBucket_
	 * add to the end of the vector for that bucket.
	 *****************************************************************/

	uint32_t index = getTTLIndex( node );
	sortedTTLs_[index].push_back( node );
}

uint32_t DNSCache::getTTLIndex( CacheListNode* node )
{
	time_t expiration = node->expiration();
	if( expiration < startTime_ )
		removeNode( node );
	uint64_t timeSinceStart = expiration-startTime_;
	uint32_t index = timeSinceStart / secondsPerBucket_;
	return index;
}

void DNSCache::removeNode( CacheListNode* node )
{
	//Check to see if it exist in the TTL list but dont require it be there
	//Same for the answers_ and authorities_
	//This function is **NOT** to preform and locking and locking
	//should be done by the caller
	
	uint32_t index = getTTLIndex( node );
	std::vector< CacheListNode* > newBucket;
	for( uint32_t i = 0; i < sortedTTLs_[index].size(); ++i )
	{
		if( node == sortedTTLs_[index][i] )
			continue;
		newBucket.push_back( sortedTTLs_[index][i] );
	}
	sortedTTLs_[index] = newBucket;

	if( authorities_.find( node->query() ) != authorities_.end() )
	{
		authorities_.erase( node->query() );
	}
		
	if( answers_.find( node->query() ) != answers_.end() )
	{
		answers_.erase( node->query() );
	}

	if( node->next() )
		node->next()->setPrevious( node->previous() );
	if( node->previous() )
		node->previous()->setNext( node->next() );

	delete node;
}

void CacheListNode::setRecords( const std::vector< DNSRecord > &records )
{
	records_ = records;
	//calculate SHORTEST expiration time
	uint32_t ttl = 0;
	for( uint32_t i = 0; i < records.size(); ++i )
	{
		if( i == 0 )
			ttl = records[i].timeToLive();
		if( ttl > records[i].timeToLive() )
			ttl = records[i].timeToLive();
	}
	time_t current = time(NULL); 
	expiration_ = current + ttl;
}

void DNSCache::setMaxTTL( const uint32_t &ttl ) 
{
	WriteLocker lock( recordLock_ );
	
	maxTTL_ = ttl;
	resizeSortedTTLList();
}

void DNSCache::resizeSortedTTLList( )
{
	uint32_t currentSize = sortedTTLs_.size();
	uint32_t numberOfBuckets = ( maxTTL_ / secondsPerBucket_ ) + 1; 
	
	if( currentSize < numberOfBuckets )
	{
		uint32_t newBucketsNeeded = numberOfBuckets - currentSize; 
		for( uint32_t i = 0; i < newBucketsNeeded; ++i )
		{ 
			std::vector< CacheListNode* > bucket;
			size_ += sizeof( bucket );
			sortedTTLs_.push_back( std::vector< CacheListNode* >() );
		}
	}
	else if ( currentSize > numberOfBuckets )
	{
		uint32_t bucketsToRemove = currentSize - numberOfBuckets;
		std::vector< CacheListNode* > bucketConcatenation;
		for( uint32_t i = numberOfBuckets - 1; i < sortedTTLs_.size(); ++i )
		{
			std::vector< CacheListNode* > currentBucket = sortedTTLs_[i];
			for( uint32_t k = 0; k < currentBucket.size(); ++k )
			{
				bucketConcatenation.push_back( currentBucket[k] );
				bucketConcatenation.back()->setExpiration( maxTTL_ );
			}
		}
		for( uint32_t i = 0; i <= bucketsToRemove; ++i )
		{
			size_ -= sizeof( sortedTTLs_.back( ));
			sortedTTLs_.pop_back(); 
		}
		sortedTTLs_.push_back( bucketConcatenation );
	}
}

void CacheListNode::setExpiration( const uint32_t &seconds )
{
	time_t currentTime = time( NULL );
	expiration_ = currentTime + seconds;
}
